package od机试;

import java.util.Scanner;

/**
 * 136最大报酬的题目描述
 *
 * 题目描述
 * 小明每周上班都会拿到自己的工作清单，工作清单内包含 n 项工作，每项工作都有对应的耗时时间（单位：小时）和报酬。
 * 工作的总报酬为所有已完成工作的报酬之和。请你帮小明安排一下工作，保证小明在指定的工作时间内工作收入最大化。
 * 输入描述
 * 输入的第一行为两个正整数 T 和 n。
 * T 代表工作时长（单位：小时，0 < T < 1000000）。
 * n 代表工作数量（1 < n <= 3000）。
 * 接下来是 n 行，每行包含两个整数 t 和 w。
 * t 代表该工作消耗的时长（单位：小时，t > 0）。
 * w 代表该项工作的报酬。
 * 输出描述
 * 输出小明在指定工作时长内工作可获得的最大报酬。
 * 示例
 * 输入
 * 复制
 * 40 3
 * 20 10
 * 20 20
 * 20 5
 * 输出
 * 30
 * 说明
 * 选择第二项和第三项工作，总耗时为 20 + 20 = 40 小时，总报酬为 20 + 5 = 25。选择第一项和第二项工作，总耗时为 20 + 20 = 40 小时，总报酬为 10 + 20 = 30。因此，最大报酬为 30。
 *
 * 解题思路：
 *  该问题可以通过动态规划解决，类似于经典的 0/1 背包问题：
 *  1：状态定义：dp[i] 表示在工作时长为 i 时，能够获得的最大报酬。
 *  2：状态转移方程：对于每个工作 (t, w)，表示该工作消耗时间 t 并获得报酬 w。我们需要决定是否选择该工作：
 *      - 如果不选择工作，则dp[i]保持不变；
 *      - 如果选择，则dp[i] = max(dp[i],dp[i-t]+w);
 *      - 从后往前遍历dp数组，确保每个工作只能被选择一次;
 *  3:初始化：dp[0] = 0，表示工作时长为 0 时的最大报酬为 0，其他 dp[i] 初始化为 0。
 *  4：结果:最终结果是 dp[T]，表示在总工作时长 T 内能获得的最大报酬。
 */
public class O_136 {

    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt(); // 工作时长
        int n = scanner.nextInt(); // 工作数量

        int[][] jobs = new int[n][2];
        for (int i = 0; i < n; i++) {
            jobs[i][0] = scanner.nextInt(); // 工作耗时
            jobs[i][1] = scanner.nextInt(); // 工作报酬
        }

        int[] dp = new int[T + 1];
        for (int i = 0; i < n; i++) {
            int t = jobs[i][0];
            int w = jobs[i][1];
            for (int j = T; j >= t; j--) {
                dp[j] = Math.max(dp[j], dp[j - t] + w);
            }
        }

        System.out.println(dp[T]);
    }

    public static void main(String[] args) {

        int[][] jobs = new int[3][2];
        jobs[0] = new int[]{20,10};
        jobs[1] = new int[]{20,20};
        jobs[2] = new int[]{20,5};

        O_136 o136 = new O_136();
        // 调用封装的函数计算最大报酬
        int maxReward = o136.calculateMaxReward(40, jobs);
        System.out.println(maxReward);
    }

    /**
     * 动态规划方法计算最大报酬
     * @param T  最大工作时长
     * @param jobs 各项工作信息，包括耗时和报酬
     * @return  最大报酬
     */
    public int calculateMaxReward(int T, int[][] jobs) {
        // 定义dp数组
        int[] dp = new int[T + 1];
        for (int i = 0; i < jobs.length; i++) {
            int t = jobs[i][0]; // 获取当前任务的时长
            int w = jobs[i][1]; // 获取当前任务的报酬
            // 从后往前遍历dp数组，确保每个工作只能选择一次，并且在总时长的范围内
            for (int j = T;j >= t; j--){
                dp[j] = Math.max(dp[j],dp[j-t]+w); // 上一个状态的最大报酬和当前状态的最大报酬取最大值
            }
        }
        return dp[T];
    }
}
